   package com.cn.codebrush.leetcode.editor.cn;

//给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。 
//
// 请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：root = [1,7,0,7,-8,null,null]
//输出：2
//解释：
//第 1 层各元素之和为 1，
//第 2 层各元素之和为 7 + 0 = 7，
//第 3 层各元素之和为 7 + -8 = -1，
//所以我们返回第 2 层的层号，它的层内元素之和最大。
// 
//
// 示例 2： 
//
// 
//输入：root = [989,null,10250,98693,-89388,null,null,null,-32127]
//输出：2
// 
//
// 
//
// 提示： 
//
// 
// 树中的节点数在 [1, 104]范围内 
// -105 <= Node.val <= 105 
// 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 
// 👍 74 👎 0



   import java.util.ArrayList;
   import java.util.Deque;
   import java.util.LinkedList;
   import java.util.List;

   public class MaximumLevelSumOfABinaryTree{


//leetcode submit region begin(Prohibit modification and deletion)
       //Definition for a binary tree node.
public static class TreeNode {

    int val;

    TreeNode left;

    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {

        this.val = val;

        this.left = left;

        this.right = right;

    }

}

       public static void main(String[] args) {
            //root = [989,null,10250,98693,-89388,null,null,null,-32127]
           Solution solution = new MaximumLevelSumOfABinaryTree().new Solution();
           TreeNode tree = new TreeNode(989);
           TreeNode a = new TreeNode(10250);
           TreeNode b = new TreeNode(98693);
           TreeNode c = new TreeNode(-89388);
           TreeNode d = new TreeNode(-32127);

           tree.right = a;
           a.left = b;
           a.right = c;
           c.right = d;

solution.maxLevelSum(tree);

       }

class Solution {
    public int maxLevelSum(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        Deque<TreeNode> deque = new LinkedList<>();
        deque.push(root);
        while(!deque.isEmpty()){
            int k = deque.size();
            int sum = 0;
            while(k>0){
                TreeNode temp = deque.poll();
                sum += temp.val;

                if(temp.left != null){
                    deque.add(temp.left);
                }
                if(temp.right != null){
                    deque.add(temp.right);
                }
                k--;
            }
            list.add(sum);

        }

        int res = 0;
        int value = list.get(0);
        for(int i=0;i<list.size();i++){
            if(value < list.get(i)){
                value = list.get(i);
                res = i;
            }
        }

        return res+1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)





















}